package com.tanzc.sort;

import com.tanzc.util.ArrayUtils;

import java.util.Date;

/**
 * <p> description: 计数排序
 * 由于计数排序需要用数组元素值做统计数组下标，所以对于不是整数的数据和超出下标范围的数据，计数排序不适用
 * </p>
 *
 * @author tanzc
 * @date 2022/1/27
 **/
public class CountSort {

    public static void main(String[] args) {
        CountSort countSort = new CountSort();
        int num = 10, max = num * 5;
        int[] arr = ArrayUtils.randomoffset(num, max, 100);
//        int[] arr = ArrayUtils.worst(num);
//        int[] arr = ArrayUtils.bad(num);
//        int[] arr = ArrayUtils.nice(num);

        int[] arr1 = new int[num];
        System.arraycopy(arr, 0, arr1, 0, num);
        ArrayUtils.printArray(arr1);

        System.out.print("计数排序-----time: ");
        Date start = new Date();
        int[] arr2 = countSort.count2(arr1);
        Date end = new Date();
        long timediff = end.getTime() - start.getTime();
        System.out.println(timediff + "ms");
        ArrayUtils.printArray(arr2);
    }

    /**
     * 计数排序
     * 计数排序不是基于元素间比较的排序算法
     * 计数排序，通过对序列中元素个数进行计数，使用一个中间数组（这个数组可以称之为统计数组），用序列元素做下标，用元素个数作为数组值
     * 然后再遍历中间数组，按数组值，将对应个数的下标值填入新数组，最后得到的新数组即为排序好的数组
     * 这种排序，出来的新数组与原数组，其稳定性根本就无从比较，因为新数组的元素都是全新的，与原数组不存在位置上的关系
     * @param arr
     * @return result
     */
    public int[] count(int[] arr) {
        int max = 0, min = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }
        // 正常思路是创建一个长度为max + 1的数组，但是这样极大可能会造成空间浪费
        int[] count = new int[max - min + 1];
        for (int i = 0; i < arr.length; i++) {
            // 由于数组长度不为max + 1，因此下标进行min的偏移
            count[arr[i] - min]++;
        }
        int j = 0;
        int[] result = new int[arr.length];
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                result[j++] = i + min;
                count[i]--;
            }
        }
        return result;
    }

    /**
     * 上面的排序是计数排序的基础思想实现，但是无法保证稳定性，当序列信息不单单包括数据值的时候，保持稳定性是很重要的
     * 通过对统计数组进行变形，可以实现排序的稳定性，但是这个我总看不太懂，需要多看看
     *
     * 改进版的计数排序
     * 对统计数组进行变形，统计数组存储的是数组下标在原数组中出现的次数。而由于数组下标本身是有序的->
     * ->因此，通过遍历统计数组，并且将每个下标的值改为其与前面下标值的和，这样，统计数组中存储的就不是下标在原数组中的出现次数，->
     * ->而是下标在原数组中出现的最后位置
     *
     * 理解上面那两句话应该就能理解计数排序改进后的思想了。
     * 然后就是填充排序数组，由于统计数组中存储的是下标在原数组中的最后位置，因此，对原数组进行倒序遍历->
     * ->这样可以保证，对于原数组中的相同元素，每次先找到靠后的元素，然后根据元素值找到统计数组中对应下标的值，这个值就是该元素->
     * ->在新数组中的位置。然后将该元素在统计数组中对应下标的值减一，也就是下次再遍历到该元素值时，在最终数组中的位置会减一
     *
     * 总之，理解改进版（稳定版）技术排序，主要就是要理解统计数组的变形，与原数组倒序遍历的原因
     * @param arr
     * @return result
     */
    public int[] count2(int[] arr) {
        int max = 0, min = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
            if (arr[i] < min) {
                min = arr[i];
            }
        }
        // 正常思路是创建一个长度为max + 1的数组，但是这样极大可能会造成空间浪费
        int[] count = new int[max - min + 1];
        for (int i = 0; i < arr.length; i++) {
            // 由于数组长度不为max + 1，因此下标进行min的偏移
            count[arr[i] - min]++;
        }
        // 统计数组变形调整
        int sum = 0;
        for (int i = 0; i < count.length; i++) {
            sum += count[i];
            count[i] = sum;
        }
        int[] result = new int[arr.length];
        // 倒序遍历原数组序列，确定各元素的最终位置
        for (int i = arr.length - 1; i >= 0; i--) {
            // 如果流程正常进行，此处是可以不进行越界判断的，所以下面的if判断可以去掉
            // 因为对于原数组序列arr中的每一个元素，必定是可以在result中找到最终位置的
            if (count[arr[i] - min] != 0) {
                result[count[arr[i] - min] - 1] = arr[i];
                count[arr[i] - min]--;
            }
        }
        return result;
    }
}
